A common goal in the development of imaging systems is the improvement in image quality. A system can be readily designed to process image data in the appropriate manner given the capabilities of the rendering system to provide high quality output if characteristics of the image data are known. However, when processing image data generated at or targeted for a different system, the characteristics of the image data are typically not known. Thus, tailoring the image processing to obtain acceptable image quality can be difficult due to the divergent processing needs required by different image types.
Consider, for example, the reproduction of images from scanned image data as might be obtained through line by line scanning of a document image. In reproducing such images, it is desirable to know the image type which may be encountered in the scanned image data as text and non-text regions are often processed differently in converting an image targeted for one printer originally to another printer. Furthermore, when processing the non-text regions, it is desirable to know the halftone frequency so that the appropriate processing can be applied. One common approach to image conversion in not-text regions is to de-screen the image and re-screen it with an optimal screen for target printer. When the halftone frequency is known, the system can avoid re-screening a low frequency halftone and eliminate the resulting moiré. In another approach, the binary dot profile is modified according to tone reproductions. Here again, knowing the original halftone frequency is required to select an appropriate correction.
To address this situation, digital reproduction devices often use automatic image segmentation techniques. An auto-segmentation operation may use any of a number of classification functions (e.g., auto-correlation, frequency analysis, pattern or template matching, peak/valley detection, histograms, etc.) to analyze image data and classify image pixels as one of several possible image classes (image types). Auto-segmentation processes typically generate a pixel classification signal, known as a segmentation tag, that identifies the pixel as a particular image class.
The use of an auto-correlation function for detection of halftones was proposed by Stoffel in U.S. Pat. No. 4,194,221. In particular, if P(x) represents the gray value of the pixel at location x, the auto-correlation as function of the image shift k computed over N number of pixels is defined as follows:
                              A          ⁡                      (            x            )                          =                              ∑                          x              =              1                        N                    ⁢                                          ⁢                                    P              ⁡                              (                x                )                                      ⨯                          P              ⁡                              (                                  x                  +                  k                                )                                                                        (        1        )            
For images that are periodic, the computed auto-correlation would have maximum peaks at shifts corresponding to the period of the periodic variations and its multiples. As a halftone image is usually periodic, the auto-correlation is well suited for detecting its frequency.
However, the use of an auto-correlation function as taught by U.S. Pat. No. 4,194,221 required multiplication which was relatively difficult and expensive to implement in hardware. In addition, this system and method required, as a practical matter, a reduction in the amount of data handled by thresholding the received image data. Such thresholding was difficult to implement and often resulted in undesirable loss of image data.
To improve the process by addressing some of the perceived limitations of the auto-correlation system and method taught by Stoffel in U.S. Pat. No. 4,194,221, a simplified version of the auto-correlation function was taught by Lin and Calarco in U.S. Pat. No. 4,811,115. This simplified version of the auto-correlation function uses logical functions and additions, rather than multiplication to approximate the auto-correlation function. This simplified auto-correlation function could be easier to implement in hardware than the multiplicative function proposed by Stoffel and taught in U.S. Pat. No. 4,194,221. In particular, the simplified version of the function as proposed is given by:
                                          A            ′                    ⁡                      (            x            )                          =                              ∑                          x              =              1                        N                    ⁢                                          ⁢                                                                P                ⁡                                  (                  x                  )                                            -                              P                ⁡                                  (                                      x                    +                    k                                    )                                                                                                    (        2        )            When the function of Eqn. (2) is applied to a stream of image data, the minimums in the resulting auto-correlated function can be detected to determine whether halftone data is present. That is, rather than the maximum, the minimum occurs at the shift corresponding to the period of image variation.
While the above techniques provide means for identifying halftones, there is always desired a method or system which provides an improvement on existing systems or methods. Such improvement may come in the form of improved performance, efficiency, and/or cost, and may include, but is not limited to one or more of reduced hardware or software complexity, reduced system resource requirements (e.g., processing and/or memory), increased speed, increased accuracy, etc. Thus, there is desired a method or system that can accurately detect halftone frequency and screen angle in a manner which may be more efficient than the existing systems and methods.
In accordance with one or more aspects of the teachings herein, there is provided an efficient method to detect frequency and angle of a binary halftone pattern which can be effectively implemented in hardware and/or software. The method employs an exclusive-or operation which can be applied locally to a small region of a binary bit map and its spatially shifted version. The resulting bits are summed over the region. The exclusive-or operation can be repeated for a range of horizontal and vertical shift values. In a halftone region, the shift at which the minimum sum occurs reflects the angle and the frequency of the halftone.
In accordance with one or more aspects of the teachings herein, there is provided a method of processing image data to determine the frequency of a binary halftone, comprising: receiving a block of pixels; applying an exclusive-or function to the block of pixels, the exclusive-or function given by:
            A      ′        ⁡          (              kx        ,        ky            )        =            ∑                        x          =          1                ,                  y          =          1                            Nx        ,        Ny              ⁢                  ⁢                  P        ⁡                  (                      x            ,            y                    )                    ⋀              P        ⁡                  (                                    x              +              kx                        ,                          y              +              ky                                )                    where P(x,y) represents a pixel intensity function at pixel position x,y in the image data, x and y define a selected pixel position, and kx and ky are selected shifts in pixel position applied to the pixel intensity function and Nx and Ny define the pixel range over which the function is evaluated; identifying a local minimum in A′(kx,ky); and determining a halftone frequency f from the identified local minimum.
In accordance with further aspects of the teachings herein there is provided a method of processing image data to determine the frequency of a halftone. The method includes receiving the image data; identifying a block of pixels within a non-text region; applying an exclusive-or function to the block of pixels, wherein the exclusive-or function given by:
                    A        ′            ⁡              (                  kx          ,          ky                )              =                  ∑                              x            =            1                    ,                      y            =            1                                    Nx          ,          Ny                    ⁢                          ⁢                        P          ⁡                      (                          x              ,              y                        )                          ⋀                  P          ⁡                      (                                          x                +                kx                            ,                              y                +                ky                                      )                                ;identifying a local minimum in A′(kx,ky); repeating the steps of identifying a block of pixels within a non-text region, applying an exclusive-or function, and identifying a local minimum for a plurality of pixel blocks within the non-text region; collecting statistics on the identified local minimums for the plurality of pixel blocks; and determining a halftone frequency f from the collected statistics.